package dubrouski.triangulation;

/*
 * ported from p bourke's triangulate.c
 * http://astronomy.swin.edu.au/~pbourke/modelling/triangulate/
 *
 * fjenett, 20th february 2005, offenbach-germany. contact:
 * http://www.florianjenett.de/
 *
 * adapted to take a Vector of Point3f objects and return a Vector of Triangles
 * (and generally be more Java-like and less C-like in usage - and probably less
 * efficient but who's benchmarking?) Tom Carden, tom (at) tom-carden.co.uk 17th
 * January 2006
 *
 * adapted to get rid of those ugly Vector and Point3f objects. it now takes an
 * ArrayList of Vector3d objects and return an ArrayList of Triangles objects.
 * see what Sun thinks about Vector objects here:
 * http://java.sun.com/developer/technicalArticles/Collections/Using/index.html
 * antiplastik, 28 june 2010, paris-france
 *
 */
import java.util.*;
import processing.core.PApplet;

public class Triangulate {

    /*
     * From P Bourke's C prototype -      *
     * qsort(p,nv,sizeof(XYZ),XYZCompare);
     *
     * int XYZCompare(void *v1,void *v2) { XYZ *p1,*p2; p1 = v1; p2 = v2; if
     * (p1->x < p2->x) return(-1); else if (p1->x > p2->x) return(1); else
     * return(0); }
     */
    private static class XComparator implements Comparator<Vector3d> {

        public int compare(Vector3d p1, Vector3d p2) {
            if (p1.getX() < p2.getX()) {
                return -1;
            } else if (p1.getX() > p2.getX()) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    /*
     * Return TRUE if a point (xp,yp) is inside the circumcircle made up of the
     * points (x1,y1), (x2,y2), (x3,y3) The circumcircle centre is returned in
     * (xc,yc) and the radius r NOTE: A point on the edge is inside the
     * circumcircle
     */
    private static boolean circumCircle(Vector3d p, Triangle t, Vector3d circle) {

        float m1, m2, mx1, mx2, my1, my2;
        float dx, dy, rsqr, drsqr;

        /*
         * Check for coincident points
         */
        if (PApplet.abs(t.getP1().getY() - t.getP2().getY()) < PApplet.EPSILON && PApplet.abs(t.getP2().getY() - t.getP3().getY()) < PApplet.EPSILON) {
            System.err.println("CircumCircle: Points are coincident.");
            return false;
        }

        if (PApplet.abs(t.getP2().getY() - t.getP1().getY()) < PApplet.EPSILON) {
            m2 = -(t.getP3().getX() - t.getP2().getX()) / (t.getP3().getY() - t.getP2().getY());
            mx2 = (t.getP2().getX() + t.getP3().getX()) / 2.0f;
            my2 = (t.getP2().getY() + t.getP3().getY()) / 2.0f;
            circle.setX((t.getP2().getX() + t.getP1().getX()) / 2.0f);
            circle.setY(m2 * (circle.getX() - mx2) + my2);
        } else if (PApplet.abs(t.getP3().getY() - t.getP2().getY()) < PApplet.EPSILON) {
            m1 = -(t.getP2().getX() - t.getP1().getX()) / (t.getP2().getY() - t.getP1().getY());
            mx1 = (t.getP1().getX() + t.getP2().getX()) / 2.0f;
            my1 = (t.getP1().getY() + t.getP2().getY()) / 2.0f;
            circle.setX((t.getP3().getX() + t.getP2().getX()) / 2.0f);
            circle.setY(m1 * (circle.getX() - mx1) + my1);
        } else {
            m1 = -(t.getP2().getX() - t.getP1().getX()) / (t.getP2().getY() - t.getP1().getY());
            m2 = -(t.getP3().getX() - t.getP2().getX()) / (t.getP3().getY() - t.getP2().getY());
            mx1 = (t.getP1().getX() + t.getP2().getX()) / 2.0f;
            mx2 = (t.getP2().getX() + t.getP3().getX()) / 2.0f;
            my1 = (t.getP1().getY() + t.getP2().getY()) / 2.0f;
            my2 = (t.getP2().getY() + t.getP3().getY()) / 2.0f;
            circle.setX((m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2));
            circle.setY(m1 * (circle.getX() - mx1) + my1);
        }

        dx = t.getP2().getX() - circle.getX();
        dy = t.getP2().getY() - circle.getY();
        rsqr = dx * dx + dy * dy;
        circle.setZ(PApplet.sqrt(rsqr));

        dx = p.getX() - circle.getX();
        dy = p.getY() - circle.getY();
        drsqr = dx * dx + dy * dy;

        return drsqr <= rsqr;
    }


    /*
     * Triangulation subroutine Takes as input vertices (PVectors) in ArrayList
     * pxyz Returned is a list of triangular faces in the ArrayList triangles
     * These triangles are arranged in a consistent clockwise order.
     */
    public static ArrayList<Triangle> triangulate(ArrayList<Vector3d> pxyz) {

        // sort vertex array in increasing x values
        Collections.sort(pxyz, new XComparator());

        /*
         * Find the maximum and minimum vertex bounds. This is to allow
         * calculation of the bounding triangle
         */
        float xmin = ((Vector3d) pxyz.get(0)).getX();
        float ymin = ((Vector3d) pxyz.get(0)).getY();
        float xmax = xmin;
        float ymax = ymin;

        Iterator<Vector3d> pIter = pxyz.iterator();
        while (pIter.hasNext()) {
            Vector3d p = (Vector3d) pIter.next();
            if (p.getX() < xmin) {
                xmin = p.getX();
            }
            if (p.getX() > xmax) {
                xmax = p.getX();
            }
            if (p.getY() < ymin) {
                ymin = p.getY();
            }
            if (p.getY() > ymax) {
                ymax = p.getY();
            }
        }

        float dx = xmax - xmin;
        float dy = ymax - ymin;
        float dmax = (dx > dy) ? dx : dy;
        float xmid = (xmax + xmin) / 2.0f;
        float ymid = (ymax + ymin) / 2.0f;

        ArrayList<Triangle> triangles = new ArrayList<Triangle>(); // for the Triangles
        HashSet<Triangle> complete = new HashSet<Triangle>(); // for complete Triangles

        /*
         * Set up the supertriangle This is a triangle which encompasses all the
         * sample points. The supertriangle coordinates are added to the end of
         * the vertex list. The supertriangle is the first triangle in the
         * triangle list.
         */
        Triangle superTriangle = new Triangle();
        superTriangle.setP1(new Vector3d(xmid - 2.0f * dmax, ymid - dmax, 0.0f));
        superTriangle.setP2(new Vector3d(xmid, ymid + 2.0f * dmax, 0.0f));
        superTriangle.setP3(new Vector3d(xmid + 2.0f * dmax, ymid - dmax, 0.0f));
        triangles.add(superTriangle);

        /*
         * Include each point one at a time into the existing mesh
         */
        ArrayList<Edge> edges = new ArrayList<Edge>();
        pIter = pxyz.iterator();
        while (pIter.hasNext()) {

            Vector3d p = (Vector3d) pIter.next();

            edges.clear();

            /*
             * Set up the edge buffer. If the point (xp,yp) lies inside the
             * circumcircle then the three edges of that triangle are added to
             * the edge buffer and that triangle is removed.
             */
            Vector3d circle = new Vector3d();

            for (int j = triangles.size() - 1; j >= 0; j--) {

                Triangle t = (Triangle) triangles.get(j);
                if (complete.contains(t)) {
                    continue;
                }

                boolean inside = circumCircle(p, t, circle);

                if (circle.getX() + circle.getZ() < p.getX()) {
                    complete.add(t);
                }
                if (inside) {
                    edges.add(new Edge(t.getP1(), t.getP2()));
                    edges.add(new Edge(t.getP2(), t.getP3()));
                    edges.add(new Edge(t.getP3(), t.getP1()));
                    triangles.remove(j);
                }

            }

            /*
             * Tag multiple edges Note: if all triangles are specified
             * anticlockwise then all interior edges are opposite pointing in
             * direction.
             */
            for (int j = 0; j < edges.size() - 1; j++) {
                Edge e1 = (Edge) edges.get(j);
                for (int k = j + 1; k < edges.size(); k++) {
                    Edge e2 = (Edge) edges.get(k);
                    if (e1.getP1() == e2.getP2() && e1.getP2() == e2.getP1()) {
                        e1.setP1(null);
                        e1.setP2(null);
                        e2.setP1(null);
                        e2.setP2(null);
                    }
                    /*
                     * Shouldn't need the following, see note above
                     */
                    if (e1.getP1() == e2.getP1() && e1.getP2() == e2.getP2()) {
                        e1.setP1(null);
                        e1.setP2(null);
                        e2.setP1(null);
                        e2.setP2(null);
                    }
                }
            }

            /*
             * Form new triangles for the current point Skipping over any tagged
             * edges. All edges are arranged in clockwise order.
             */
            for (int j = 0; j < edges.size(); j++) {
                Edge e = (Edge) edges.get(j);
                if (e.getP1() == null || e.getP2() == null) {
                    continue;
                }
                triangles.add(new Triangle(e.getP1(), e.getP2(), p));
            }

        }

        /*
         * Remove triangles with supertriangle vertices
         */
        for (int i = triangles.size() - 1; i >= 0; i--) {
            Triangle t = (Triangle) triangles.get(i);
            if (t.sharesVertex(superTriangle)) {
                triangles.remove(i);
            }
        }

        return triangles;
    }
}
